package com.mt.sort;

import java.util.Arrays;
/**
 * @ClassNameAbstractSort
 * @Description 归并排序
 * @Author
 * @Date2021/7/3 上午10:39
 * @Version V1.0
 **/
public class MergerSort {

    public static void process(int[] arr,int L,int R){
        if (L == R){
            return;
        }
        int mid = L+((R-L) >>1);
        process(arr,L,mid);
        process(arr,mid+1,R);
        merger(arr,L,mid,R);
    }

    private static void merger(int[] arr, int L, int M, int R) {
        int[] help = new int[R-L+1];
        int i=0;
        int p1 = L;
        int p2 = M+1;
        while (p1 <=M && p2 <=R){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <=M){
            help[i++] = arr[p1++];
        }

        while (p2 <=R){
            help[i++] = arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[L+i] =help[i];
        }
    }

    public static void main(String[] args) {
        int[] arr ={3,7,4,2};
//        int[] arr ={3,7,4,2,4,3,2,22};
        System.out.println(Arrays.toString(arr));
        process(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}
